package com.gitee.ywj1352.算法.week01;

/**
 *
 * 蒙蔽的时候： 暴力？ 基本情况
 *
 * 找  最近 重复子问题
 * 因为 ：if else  for while ，
 *
 *
 * 1。 n=1 ： 1
 * 2。 n=2 ： 2
 * 3。 n=3 ：f(3) = f(2) + f(1)
 * n.  f(n) = f(n-1) + f(n-2)  Fibonacci
 *
 */
public class ClimbStairs {

    // 本质上是一个 Fibonacci 问题
    // 是保存n的arr 但是 我们这里可以只保留 F(n) = F(n-1) + F(n-2)
    public static int climbStairs(int n) {
        int[] a = new int [n];
        if (n > 2){
            a[0] = 1;
            a[1] = 2;
            for (int i = 2; i < n; i++) {
                a[i] = a[i-1] + a[i-2];
            }
            return a[n-1];
        }
        return n;
    }


    //这里只保留 三个楼梯的步骤
    public static int climbStairs2(int n) {
        int a = 1,b = 2,c = 0;
        if (n < 3)
            return n;
        for (int i = 2; i < n; i++) {
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }




    public static void main(String[] args) {
        System.out.println(climbStairs2(54));
        System.out.println(climbStairs(54));
    }
}







